package MyListNode;

/**
 * 判断链表的环 环形链表的位置
 */
public class Leetcode0142 {
    public static ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(true){
            // 两个判断都是fast
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        while (fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);

        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = c;

        ListNode res = detectCycle(a);
        System.out.println(res.val);
    }

}
